package interview.modifiedbinarysearch;

public class ModifiedBinarySearch {
	public int find(String[] array, String target) {
		int left = 0;
		int right = array.length - 1;
		int mid;
		while(left <= right) {
			mid = left + (right - left) / 2;
			int temp = mid;
			while(array[mid].equals("") && mid <= right) {
				mid++;
			}

			if(mid > right) {
				mid = temp;
				while(array[mid].equals("") && mid >= left) {
					mid--;
				}
			}

			if(mid < left) {
				return -1;
			}

			if(array[mid].equals(target)) {
				return mid;
			} else if (array[mid].compareTo(target) == 1) {
				right = temp - 1;
			} else {
				left = temp + 1;
			}
		}

		return -1;
	}
}
